#include <iostream>
#include <vector>
using namespace std;
//
//class A{};
//
//int main()
//{
//	A a;
//	return 0;
//}

void qsort(vector<int>& arr, int l, int r)
{
	if (l >= r) return;
	int key = arr[rand() % (r - l + 1) + l];
	int left = l - 1, right = r + 1;
	int i = l;
	while (i < right)
	{
		if (arr[i] < key) swap(arr[i++], arr[++left]);
		else if (arr[i] == key) ++i;
		else swap(arr[i], arr[--right]);
	}
	qsort(arr, l, left);
	qsort(arr, right, r);
}

int main()
{
	vector<int> arr = { 1,3,6,4,3,1,5,2,7,9,8,0 };
	int n = arr.size();
	qsort(arr, 0, n - 1);
	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}